The present invention relates to a data processing device or data processor such as a micro-processor with a cache memory or a DSP (Digital Signal Processor), and in particular to a technique effectively applied to a cache control technique using a way predicting function.
In the data processing device such as a microprocessor or a DSP, an on-chip cache memory capable of high-speed operation is generally mounted to minimize the amount of data transfer from the processor to an external memory and improve performance. This configuration enables the processor to hide an access cycle to the external memory when a hit occurs in the cache memory, and hence achieve high performance. From the viewpoint of power consumption, the processor can also reduce the power requirements for memory control, though the cache memory itself consumes power, because of no need to drive an external input/output pin or an external input/output buffer circuit. Thus the use of such a cache memory can contribute to lower power consumption for the entire processor.
To form a cache memory, there are mapping methods for bringing external memory data into correspondence with data in the cache on a fixed block basis. The mapping methods include a direct mapping method, a set associative method and a full associative method.
Here, if the size of a block is B bytes and the number of blocks is “c,” a block number “m” including the bytes of an external memory address a will be an integral number part of “a/B.”
In the direct mapping method, the block of the external memory with the number “m” is uniquely mapped to a block in the cache memory with a number represented by a modulo operational expression “m mod c.” In the direct mapping, if plural blocks possibly allocated to the same block in the cache are used at the same time, a collision will occur and the cache hit rate will be reduced. In contrast, the full associative method is to map any block in the external memory to any block in the cache memory. However, in the full associative method, associative retrieval needs to be performed for all the blocks at each access, which is hard to realize in a practical cache capacity. Therefore, the set associative method that is in-between of both is generally put to practical use. In the set associative method, a unit of n (N=2, 4, 8 or so) blocks in the cache is defined as a set, and to this set the direct mapping method is applied while to the blocks in the set the full associative mapping is applied so that the merits of both methods will be used. By the value n, this method is called an n way set associative method.
From the viewpoint of access time, the set associative method, however, is inferior to the direct mapping method. Generally speaking, one line (one cache entry) of the cache consists of a tag indicating an address stored in the cache and stored data, and which block (way) data in the set should be read out depends on a result of comparison between the access address and the tag. In the direct mapping method, since data to be read out is uniquely determined by the access address, the direct mapping method is the most advantageous for the time required to read out the cache.
The direct mapping method is the most advantageous in terms of power consumption as well. This is because the set associative method is required not only to read out the tags of all the blocks (ways) in the set, but also to determine or confirm the readout data at a high speed, which generally needs to perform control for reading out data of all the way candidates without waiting for a decision of a hit way.
There is another method, called a way-predictive set-associative method, which can enjoy the merits of both the direct mapping method and the set associative method as described above, that is, high performance resulting from a high cache hit rate of the set associative method and a speedup resulting from the fact that the direct mapping method can perform cache retrieval at each access in a short time.
In the way-predictive set-associative method, since the read-out data can be determined or confirmed without waiting for the decision of a hit way by predicting a unique way with a reference line existing thereon independently of the tag comparison, high-speed reading in the direct mapping method can be performed while achieving a high hit rate in the set associative method. An example of this kind of way-predictive set-associative method is described in JP-A-07-334423.